The present invention relates to computer systems, and more particularly to a method and system for providing a hardware sort which is simple to design, simple to use, fast, and applicable to computer graphics system.
Many computer systems must sort items based on the value of a key in order to achieve certain functions. Such computer systems conventionally employ a software sort. For example, computer graphics systems may utilize a software sort in order to render an image. In current computer graphics systems, images of three-dimensional objects can be depicted on a two dimensional display. In order to give the illusion of depth, computer graphics systems use each objects xe2x80x9cz value,xe2x80x9d the distance of each object to the viewing plane. In particular, the objects are ordered based on each object""s z value. Thus, the key for such sort is the z value. Once the objects are sorted according to their z values, the computer graphics system can correctly blend the colors of translucent objects and opaque objects that can be seen through the translucent objects to achieve the proper color to be displayed for each pixel.
In a conventional computer graphics system, the software sort occurs when a display list is generated through an application. The display list orders three-dimensional objects based on a key, typically the z value. The display list typically orders translucent object from back to front. Thus, the display list sorts translucent objects. Although they may appear on the display list, opaque objects are typically sorted using a conventional Z buffer.
Placing the objects in the order prescribed by the display list allows the computer system to properly depict the images of the three-dimensional objects on the display. Hardware in the computer graphics system utilizes the display list, a frame buffer, and a z buffer to render the three-dimensional objects in the order dictated by the display list. The frame buffer and z buffer describe a portion of a three-dimensional object that is to be rendered. The frame buffer includes data such as color and alpha values for the portion of the object, while the z buffer includes corresponding the z values. The conventional computer graphics system provides the objects described in the frame and z buffers to the display screen in the order prescribed by the display list. Consequently, solid objects are rendered first, then translucent objects are rendered from back to front. Thus, the display list generated by software is used to render the three-dimensional objects.
Although conventional computer graphics systems are capable of depicting three-dimensional objects, the software sort required to provide the display list can be relatively slow. If the software sort is optimized, the sort time can be reduced to a limited extent. However, development time for the software sort is significantly increased. Moreover, changes to the display list and the software sort creating the display list may be difficult to implement. Finally, since the hardware requires a display list in order to properly render the objects, the computer system is limited to using those applications which provide a sorted display list. Without the display list and the attendant software sort, the computer system may not be able to properly depict three-dimensional objects.
Accordingly, what is needed is a system and method for sorting items which does not require a sort performed by software. It would also be beneficial if the system and method could be implemented in a computer graphics system for providing a two dimensional image of three-dimensional objects. The present invention addresses such a need.
The present invention provides a method and system for providing a sort in a computer system. The sort is based on a plurality of values of a key. Each of the plurality of items has an associated value of the plurality of values. The method and system comprise providing a new item of the plurality of items to a plurality of sort cells. The new item includes a new value of the plurality of values. The plurality of sort cells is for sorting the plurality of items. Each sort cell is for sorting a corresponding item of the plurality of items. The corresponding item has a corresponding value of the plurality of values. The method and system further comprise comparing the new value to the corresponding value for each of the plurality of sort cells to determine whether to retain the corresponding item. Each of the plurality of sort cells retains the corresponding item if the corresponding item is to be retained. For each of the plurality of sort cells, the method and system determine whether to accept the new item or an item corresponding to the previous sort cell if the corresponding item is not to be retained. If the corresponding item is not to be retained, the method and system allow a sort cell to accept the new item or the item corresponding to the previous sort cell.
According to the system and method disclosed herein, the present invention provides a hardware sort which is simple to implement and modify, fast, and applicable to computer graphics systems.